package com.zyk.leetcode;

import com.zyk.util.TreeUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhangsan
 * @date 2021/5/10 8:35
 */
public class C872 {


    public static boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> allLeaf1 = getAllLeaf(root1);
        List<Integer> allLeaf2 = getAllLeaf(root2);
        int N = allLeaf1.size();
        if (allLeaf2.size() != N) return false;
//        System.out.println(allLeaf1);
//        System.out.println(allLeaf2);
        for (int i = 0; i < N; i++) {
            if (!allLeaf1.get(i).equals(allLeaf2.get(i))) {
                return false;
            }
        }
        return true;
    }

    public static List<Integer> getAllLeaf(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        posRecur(root, res);
        return res;
    }

    public static void posRecur(TreeNode root, List<Integer> list) {
        if (root.left == null && root.right == null) {
            list.add(root.val);
        }
        if (root.left != null) {
            posRecur(root.left, list);
        }
        if (root.right != null) {
            posRecur(root.right, list);
        }
    }


    // for test
    public static void main(String[] args) {
        Integer[] nums1 = {3, 5, 1, 6, 2, 9, 8, null, null, 7, 4};
        Integer[] nums2 = {3, 5, 1, 6, 7, 4, 2, null, null, null, null, null, null, 9, 8};
        TreeNode root1 = TreeUtil.generateTreeByArr(nums1);
        TreeNode root2 = TreeUtil.generateTreeByArr(nums2);
        System.out.println(leafSimilar(root1, root2));
    }

}
